In modern digital data transmission (wireless telephony, wireless data transmission, optical disk transmission to a player, music players receiving music data, and so on), a source encoder can compress the data to be transmitted for efficiency and then a channel encoder can receive the compressed data and add redundancy to it to protect the data against noise in the transmission channel. The receiver (sometimes referred to as the “sink”) at the other end of the channel receives the encoded data and uses a channel decoder to perform the inverse of channel encoding, followed by a source decoder which performs the inverse of source encoding. The decoded information is then played by the sink, e.g., by an optical disk player or music player or receiving telephone as audio, or is otherwise used and/or stored by the receiver.
Present principles focus on channel encoding for transmission of data that possibly contain redundancies introduced purposefully to improve the chances of recovery from error at the receiver. Channel encoding typically works by sending a piece of data sought to be communicated, referred to as a “data word,” through a transformation to produce a “codeword” that is better protected against errors than the data word from which it is derived, and thus is more suitable for transmission than the data word. For present purposes suffice it to say that linear block encoders, which multiply a data word using a matrix, have been used for this purpose because they are able to achieve an acceptable tradeoff of offering significant (albeit not absolute) protection against noise, commonly expressed in terms of the error rates such as bit error rates (BER) that result from noise, while being of sufficiently “low complexity” in terms of the amount of computation they require. Higher complexity encoding schemes that reduce the BER of a received signal but require too much computation for expected data transmission rates are of little practical use.
A newer type of linear block code is the polar code, which improves on older codes by being able to achieve channel capacity, i.e., by being able to encode data such that the full capacity of the transmission channel can be exploited. Channel polarization refers to the fact that given a binary-input discrete memoryless channel W with symmetric capacity I(W), it is possible to synthesize, out of N independent copies of W, a second set of N binary-input channels WN(i), 1≤i≤N such that as N becomes large, a fraction I(W) of the synthesized channels become near perfect while the remaining fraction of channels become near useless. Codes constructed on the basis of this idea are called polar codes. Non-systematic polar encoders effect polar coding by collecting an input data word d and a fixed word b into a transform input word u and by multiplying it with a transform matrix G to render a codeword x, i.e., x=uG.
The transform matrix G used in polar codes is based on Kronecker products, and its dimension is established as appropriate for the desired channel rate or capacity. Polar coding essentially amounts to selecting some of the elements of the transform input word u to carry the data word d while “freezing’ (not using for encoding) the remainder of the elements of the transform input word. The elements of the transform input word that are selected to carry the data word d are those that in effect “see” the relatively good channels created by channel polarization, while the elements of b that are frozen “see” the relatively bad channels. The paper E. Arikan [Arik1], “Channel Polarization: A Method for Constructing Capacity-Achieving Code for Symmetric Binary-Input Memoryless Channels,” IEEE Trans. Inf. Theory, volume 55, pages 3051-3073 (July 2009), incorporated herein by reference and included in the file history of this application, introduced polar codes and describes how to carry out channel polarization and transmit data reliably in the presence of noise using only the “good” channels. Polar codes have attracted interest for practical applications and several methods have been proposed for improving their performance.
One method that was proposed for enhancing polar coding performance is systematic encoding [Arik2]. Systematic encoding of polar codes has several benefits. First, it improves the Bit Error Rate (BER) performance of polar codes as shown in [Arik2, Li]. Second, it allows construction of “turbo-like” polar codes as pointed out in [Arik2] and studied in detail in [Wu]. Third, systematic encoding of polar codes has also been beneficially applied to develop methods for Hybrid Automatic Repeat request (HARQ) schemes, as in [Feng, Moha]. Recursive methods for carrying out systematic encoding of polar codes in a low-complexity manner have been disclosed in [Arik3]. Specific methods that utilize the recursive principles in [Arik3] for systematic polar encoding appeared in [Chen, Sark1, Sark2, Vang].
Recent work on polar coding within standardization bodies, such as [Huaw1], [Huaw2], [Huaw3], and [Intel], propose certain modifications to polar coding that are not compatible with existing methods of systematic encoding of polar codes. In these works, two major modifications are proposed that are of significance for present purposes. First, a certain amount of redundancy, usually in the form of a cyclic redundancy check (CRC), is inserted into the data so as to improve the performance of a list decoder at the receiver [Tal, Huaw1, Huaw2, Intel]. Second, “puncturing” is applied, as a method adjusting the length and rate of the polar code to desired values [Huaw3, Wang]. These above-described methods of “data-checks” and “puncturing” have been proposed within the framework of non-systematic encoding of polar codes.
As recognized herein, however, data-checks and puncturing as proposed in the cited works distort the structure of polar codes and render existing methods of systematic encoding of polar codes inapplicable.
Present principles critically recognize that a systematic encoder for polar codes that allows insertion of data-checks into the transmitted signal in such a way that there is no concomitant performance penalty relative to the case of non-systematic encoding is desirable in order to maximize channel capacity exploitation, maximize immunity from noise, while exhibiting a low computation complexity to enable it to feasibly operate in expected data transmission environments.